﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleVigenereMeter
{
    class BoyerMore
    {
        public static ArrayList Match(String text, String pattern)
        {
            ArrayList arrayInt = new ArrayList();
            int[] last;
            int textLength, patternLength, textIter, patternIter, lo;

            last = BuildLast(pattern);
            textLength = text.Length;
            patternLength = pattern.Length;
            textIter = patternLength - 1;

            if (textIter > textLength - 1)
            {
                return arrayInt;
            }

            patternIter = patternLength - 1;
            do
            {
                if (pattern[patternIter] == text[textIter])
                {
                    if (patternIter == 0)
                    {
                        arrayInt.Add(textIter);
                        textIter += patternLength;
                        patternIter = patternLength - 1;
                    }
                    else
                    {
                        --textIter;
                        --patternIter;
                    }
                }
                else
                {
                    lo = last[text[textIter]];
                    textIter = textIter + patternLength - Math.Min(patternIter, lo + 1);
                    patternIter = patternLength - 1;
                }
            } while (textIter < textLength);

            return arrayInt;
        }

        public static int[] BuildLast(string pattern)
        {
            int[] last = new int[256];
            int length = pattern.Length;

            // Init
            for (int i = 0; i < 256; ++i)
            {
                last[i] = -1;
            }

            // build last
            for (int i = 0; i < length; ++i)
            {
                last[(byte)pattern[i]] = i;
            }

            return last;
        }
    }
}
